COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00012 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\rm
\line{\sevenrm a01.tex[358,phy] \today\hfill}

\parskip 5pt
\line{\bf Fibonacci Arithmetic\hfill}

We consider the problem of programming efficient operations such as
$\lfloor x\rfloor$, $\{x\}=x-\lfloor x\rfloor$, $\lfloor x\rfloor y$,
$\lfloor x/y\rfloor$, $x\bmod y$, and ${\rm GCD}(x,y)$, for a computing
device limited to a bounded number of real-valued storage cells, the
functions $x+y$ and $x-y$, and the test $x≥0$.

The usual binary methods are inefficient. For example, to compute $\{x\}$
by repeatedly subtracting powers of~2 apparently requires time
$\theta(\log x)↑2$ because there is no way to divide by~2 or to store
a table of powers of~2. Instead of basing algorithms on the sequence
of powers of~2, we base them on the sequence of Fibonacci numbers:
$$\eqalign{F↓0&=0\cr
F↓1&=1\cr
F↓{i+2}&=F↓i+F↓{i+1}\,.\cr}$$
{}
$$\vcenter{\halign{$\hfil#\hfil$\qquad%
&$\hfil#$\quad&$\hfil#$\quad&$\hfil#$\quad&$\hfil#$\quad&$\hfil#$\quad&$\hfil#$\quad%
&$\hfil#$\quad&$\hfil#$\quad&$\hfil#$\quad&$\hfil#$\quad&$\hfil#$\cr
i&-4&-3&-2&-1&0&1&2&3&4&5&6\cr
\noalign{\smallskip}
F↓i&-3&2&-1&1&0&1&1&2&3&5&8\cr}}$$

From a pair $P↓i=\langle F↓i,F↓{i+1}\rangle$, one obtains
$P↓{i+1}=\langle F↓{i+1},F↓i+F↓{i+1}\rangle$, 
$P↓{i-1}=\langle F↓{i+1}-F↓i,F↓i\rangle$, $(i=0)≡(F↓i=0)$, or
$(i≥0)≡(F↓i≥0∧F↓{i+1}>0)$. Starting with $P↓0=\langle 0,1\rangle$,
one gets~$P↓i$ in~$|i|$ additive steps. More generally, for any real~$r$,
one gets $rP↓i=\langle rF↓i,rF↓{i+1}\rangle$, starting with
$rP↓0=\langle 0,r\rangle$, in~$|i|$ additive steps by the same recurrences.

If $F↓i≤r<F↓{i+1}$, $0≤r-F↓i<F↓{i-1}$. 
Define the Fibonacci intervals $I↓j=[F↓j,F↓{j+1})$.
Every non-negative~$r$ falls into some~$I↓j$, $j≥0$, $j≠1$. If $r≥1$, then $j≥2$,
and $r-F↓j$ falls into some~$I↓k$ with $k≤j-2$. This permits the
following algorithm to decompose any non-negative real~$r$ into
$\{r\}+F↓{i↓1}+F↓{i↓2}+\cdots +F↓{i↓n}$, where the subscripts are non-negative,
$i↓1≥2$, and the subscripts increase by at least~2. The algorithm uses
three variables, maintains the invariant $(\exists i≥0)(x=F↓i,y=F↓{i+1})$,
and prints the decomposition of~$r$ in reverse order.

\smallskip
\halign to\hsize{\qquad\qquad{\tt#}\hfil
\tabskip=0pt plus 1fil
&\hfill#
\tabskip=0pt
\cr
READ $r$\cr
$\langle x,y\rangle←\langle 0,1\rangle$\cr
WHILE $r≥1$ DO\cr
\qquad BEGIN\cr
\qquad IF $r≥y$ THEN $\langle x,y\rangle ←\langle y,x+y\rangle$\hfill&(A)\cr
\qquad ELSE IF $x≤r$ THEN\cr
\qquad\qquad BEGIN\cr
\qquad\qquad $r←r-x$\hfill&(B)\cr
\qquad\qquad WRITE $x$\cr
\qquad\qquad END\cr
\qquad ELSE $\langle x,y\rangle ←\langle y-x,x\rangle$\hfill&(C)\cr
\qquad END;\cr
WRITE $r$\cr}

\vfill\eject

\noindent
The algorithm performs step (A) $i↓n$ times, step (C) $i↓n-i↓1$ times,
and step~(B) $n$~times. Since $i↓n≥2n$ and $i↓1≥2$,
 the total number of arithmetic
operations is at most ${5\over 2}i↓n-2$. Since $i↓n≤[?]\log r$, the
algorithm takes at most $[?]\log r$ arithmetic operations. 

By accumulating the values of $x$ written by the above algorithm, one
computes $\lfloor r\rfloor$. In fact, for arbitrary reals $a$ and~$b$,
by maintaining the invariant $\langle u,v\rangle =a\langle x,y\rangle$,
 one can readily compute
$a\lfloor r\rfloor +b$. For integer~$r$, this performs cumulative
multiplication in $[?]\log r$ arithmetic steps.

To get $q=\lfloor a/b\rfloor$ and $r=a-qb$ is similar. Since $a/b$ can
not in general be calculated, we simulate decomposing $a/b=\lfloor a/b\rfloor
+F↓{i↓1}+\cdots +F↓{i↓n}$ by decomposing
$a=b\lfloor a/b\rfloor+bF↓{i↓1}+\cdots +bF↓{i↓n}$.

\smallskip
\halign{\qquad\qquad {\tt #}\hfill\cr
READ $a$, $b$\cr
$\langle x,y,u,v,q\rangle ←\langle 0,1,0,b,0\rangle$\cr
WHILE $a≥b$ DO\cr
\qquad BEGIN\cr
\qquad IF $a≥v$ THEN $\langle x,y,u,v\rangle ←\langle y,x+y,v,u+v\rangle$\cr
\qquad ELSE IF $u≤a$ THEN $\langle a,q\rangle ←\langle a-u,q+x\rangle$\cr
\qquad ELSE $\langle x,y,u,v\rangle ←\langle y-x,x,v-u,u\rangle$\cr
\qquad END;\cr
WRITE $q$, $a$\cr}

\smallskip
\noindent
The invariants include $(\exists j)(\langle x,y\rangle =I↓j,\langle u,v\rangle
=bI↓j,a=a↓0-qb)$.

To get the greatest common divisor is now a matter of performing Euclid's
algorithm using Fibonacci division. Because Fibonacci division and binary
division take the same time to within a constant factor, the same is true
for the GCD. The following GCD algorithm has been hand-tuned, and uses
only three registers.

\smallskip
\halign{\qquad\qquad {\tt #}\hfill\cr
READ $a$, $c$\cr
$b←a$\cr
REPEAT\cr
\qquad BEGIN\cr
\qquad IF $b≤c$ THEN $\langle a,b\rangle ←\langle b,a+b\rangle$\cr
\qquad ELSE IF $a=b$ THEN\cr
\qquad\qquad IF $c=0$ THEN RETURN $a$\cr
\qquad\qquad ELSE $\langle a,b,c\rangle ←\langle c,c,a\rangle$\cr
\qquad ELSE IF $c<a$ THEN $\langle a,b\rangle ←\langle b-a,a\rangle$\cr
\qquad ELSE $c←c-a$\cr
\qquad END\cr}

\smallskip
\noindent
Invariants include: $(\exists j\in{\bf N})\bigl(\langle a,b\rangle\hbox{ is a
multiple of }I↓j,{\rm GCD}(a,b,c)={\rm GCD}(a↓0,c↓0)\bigr)$.

The above algorithm is readily modified to print the quotients, providing
the continued fraction representation of $a/b$. It terminates iff $a/b$
is rational. 

\vfill\eject

Show the algorithm takes time
$$\log\left({\max(a,b)\over {\rm GCD}(a,b)}\right)[?]\,.$$


\bigskip
\parindent0pt
\copyright 1987 Robert W. Floyd.
First draft (not published)
September 9, 1987.
%revised date;
%subsequently revised.

\bye